来源
来源于数组支持按下表访问的特性，是数组的拓展。
构造：首先根据数据确定哈希函数，接着选择冲突解决方法，最后构造散列表，再写上需要的增加、查找、删除的方法。
插入：根据key键值，经过哈希函数，得到哈希值，插入表中。
查找：根据key值查找。
三个问题：如何设计散列函数，如何根据装载因子动态扩容，以及如何选择散列冲突解决方法。
设计散列函数
定义
key值通过哈希函数之后，数据散列到列表中。
4个要求
哈希之后，值为大于0的整数，对应到数组的下标
同一个key的哈希结果相同
哈希之后的值均匀分布
哈希方法不能太复杂
根据装载因子动态扩容 rehash
原因
装载因子——给定一个能存放n个元素的、具有m个槽位的散列表T：
定义T的装载因子：α = n / m
对于动态的数据集，一开始无法知道其大小，其频繁的插入和删除，可能导致装载因子过大或者过小。此时我们需要动态扩容。
方式
插入数据的时间复杂度O(1)，但是某次达到装载因子阈值的插入时需要重新对原来数据进行hash操作，再放入新元素。非常耗时，需要优化放入分批扩容。
对于插入：获取一个新的2倍大小的哈希表，将新元素哈希之后插入，同时选择原哈希表中的一个数据插入新表，直至原哈希表为空。
对于查找：现在新表中查询，再查找旧表。
选择冲突解决的办法
定义
不同的key值散列之后，有可能获得同样的值，发生散列冲突
2个方法
空间寻值法：
1 种类：
- 线性寻址：index + i
- 平方寻址：index + i^2
- 二次哈希：经过两次哈希函数得到的值
2 对应方法
增加：冲突后，往后找寻空位置放置元素
查找：哈希之后的值不是要找寻的元素时，往后面继续寻找。找到返回true；若找到空，则说明不存在该元素。
删除：注意。删除后标记delete，而不知直接删除。否则查找方式受影响。
3 缺点
- 装载因子不能过大，因此要求的空位要足够，需要较大的内存
- 会发生一次集群、二次集群，经过哈希之后的值都分布在某一段，插入和查找的时间成本变多
链接法
- 方法：将冲突元素装在以h(k)开头的链表
- 查找时间：为Θ(1 + α)，查找操作最坏情况下，需要常数时间。
- 优点：装载因子可以较大，要求的内存少
- 优化：如果链表中元素较多的时候，我们可以使用改造为其他高效的动态数据结构（树等），及时最极端情况下也只是退化为一棵树，查找时间还是0(log n)。
例子
工业散列表：Java 中的 HashMap
1 初始大小：默认16，预先知道数据大小可以设计出适合大小避免rehash
2 装载因子和动态扩容：0.75，自动扩容为2倍
3 散列冲突：链接法。jdk1.8版本中，优化链表，如果链表>8，则转化为红黑树，查找更快；<8时，变为链表，因为树结构平衡维护。
word的拼写检查
1 数据存储的数据结构：50w个英文单词不超多10M，存储于哈希表中。
2 单词比对：对于每次输入的单词，作为key值，hash之后，查找哈希表，若查找不到，则标注拼写错误。
总结
当数据量比较小、装载因子小的时候，适合采用开放寻寻址法。
数据量大，空间不足，使用链表法。